package com.sloera.algorithm.backpack;

import java.util.Scanner;

/**
 * <a href="https://sloera.gitee.io/post/learn/algorithm/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/">背包问题</a>
 *
 * <p>
 * class com.sloera.algorithm.backpack
 * user sloera
 * date 2022/3/21
 */
public class Solution {
    public static void main(String[] args) {
        int value = backPackZeroOneCompression();
        System.out.println(value);
    }

    /**
     * 10 4
     * 2 1
     * 3 3
     * 4 5
     * 7 9
     *
     * @return int
     * @date 2022/3/21
     */
    private static int backPackZeroOne() {
        int[][] dp = new int[35][205];
        // 重
        int[] w = new int[35];
        // 价值
        int[] v = new int[35];

        // m 背包容量
        // n 多少个物品
        int m = 0, n = 0;
        final Scanner scanner = new Scanner(System.in);
        if (scanner.hasNextInt()) {
            m = scanner.nextInt();
            n = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }

        // 循环物品
        for (int i = 1; i <= n; i++) {
            // 循环容量
            for (int j = 1; j <= m; j++) {
                if (w[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }
        // 输出dp表
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        return dp[n][m];
    }

    private static int backPackZeroOneCompression() {
        int[] dp = new int[0];
        // 重
        int[] w = new int[35];
        // 价值
        int[] v = new int[35];

        // m 背包容量
        // n 多少个物品
        int m = 0, n = 0;
        final Scanner scanner = new Scanner(System.in);
        if (scanner.hasNextInt()) {
            m = scanner.nextInt();
            n = scanner.nextInt();
            dp = new int[m + 1];
        }
        for (int i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }

        // 循环物品
        for (int i = 1; i <= n; i++) {
            // 循环容量 注意倒序
            for (int j = m; j >= 1; j--) {
                if (w[i] > j) {
                    // 压缩后
                    dp[j] = dp[j];
                } else {
                    // 压缩后
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                }
            }
        }
        // 输出dp1表
        for (int i = 0; i <= m; i++) {
            System.out.print(dp[i] + " ");
        }
        System.out.println();
        return dp[m];
    }

}
